package top100.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/26 9:17
 * @description:
 */
public class Solution994 {
    int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int orangesRotting(int[][] grid) {
        int M = grid.length;
        int N = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        //count 表示新鲜橘子的数量
        int count = 0;
        //找出所有新鲜橘子和腐烂橘子
        for (int r = 0; r < M; r++) {
            for (int c = 0; c < N; c++) {
                if (grid[r][c] == 1) {
                    count++;
                } else if (grid[r][c] == 2) {
                    //腐烂的橘子放入队列
                    queue.add(new int[]{r, c});
                }
            }
        }
        //round 表示腐烂的轮数
        int round = 0;
        while (count > 0 && !queue.isEmpty()) {
            round++;
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                //拿出腐烂橘子
                int[] orange = queue.poll();
                int r = orange[0];
                int c = orange[1];
                for (int j = 0; j < 4; j++) {
                    int newR = r + direction[j][0];
                    int newC = c + direction[j][1];
                    //上邻点，判断是否边界，并且上放是否是健康的橘子
                    if ((newR >= 0 && newR < M) && (newC >= 0 && newC < N) && grid[newR][newC] == 1) {
                        //感染它
                        grid[newR][newC] = 2;
                        //好橘子-1
                        count--;
                        //把被感染的橘子放入队列
                        queue.add(new int[]{newR, newC});
                    }

                }

            }
        }
        //此时如果还有健康的橘子返回-1,否则返回层级
        if (count > 0) {
            return -1;
        } else {
            return round;
        }
    }

    public static void main(String[] args) {
        Solution994 solution = new Solution994();
        int [][]grid = {{2,1,1},{1,1,0},{0,1,1}};
        System.out.println(solution.orangesRotting(grid));
    }
}
